
算法竞赛的树和现实生活中的树长得一样，只不过我们习惯于处理问题的时候把树根放到上方来考虑。

这种数据结构看起来像是一个倒挂的树，因此得名。

形式化的定义：

\begin{itemize}
\item 有 $n$ 个节点， $n-1$ 条边的连通无向图
\item 无向无环连通图
\item 任意两个节点之间有且仅有一条简单路径的无向图
\end{itemize}

\subsection{有关树的定义}

\subsubsection{森林}

每个连通分量（连通块）都是树的图

\subsubsection{生成树}

一个图的生成子图，同时要求是树。

\subsubsection{有根树}

指定了一个点是根的树

\subsubsection{无根树}

没有指定一个根节点的树

\subsubsection{深度}

\paragraph{节点的深度}

到根节点的距离（最短路径的长度）

\paragraph{树的深度}

所有节点的深度的最大值

\subsubsection{父亲}

一个节点到根节点的路径上的第二个节点

\subsubsection{祖先}

一个节点到根节点的路径上，除了它本身外的所有节点

\subsubsection{子节点}

如果 $u$ 是 $v$ 的父亲，那么 $v$ 是 $u$ 的子节点。

\subsubsection{兄弟}

同一个父亲的多个子节点互为兄弟

\subsubsection{后代（子孙）}

子节点和子节点的后代

或者理解成：如果 $u$ 是 $v$ 的祖先，那么 $v$ 是 $u$ 的后代。

\subsubsection{度数}

\paragraph{无根树}

和一个点相关的边的个数

\paragraph{有根树}

子节点个数

\subsubsection{叶节点}

\paragraph{无根树}

度数不超过 $1$ 的节点

\begin{QUESTION}{为什么不是度为 $1$？}{}
考虑 $n = 1$ 的时候。

\end{QUESTION}


\paragraph{有根树}

没有子节点（度数为 $0$）的节点

\subsubsection{子树}

删掉与父亲相连的边后，该节点所在的子图

\subsection{特殊的树}

\subsubsection{只有一个节点}

没有边

$n = 1, m = 0$

\subsubsection{链}

点 $i$ 的父亲为 $i - 1$。

树的深度为$n - i$。

\subsubsection{菊花}

所有非根节点的父亲均为根节点。

树的深度为 $1$。

\subsubsection{二叉树}

每个节点最多只有两个儿子（子节点）的树

\paragraph{满二叉树}

Full binary tree，每个节点度数为 0 或者 2。换言之，每个节点或者是树叶，或者左右子树均非空。

\paragraph{完全二叉树}

Complete binary tree，只有最下面两层节点的度数可以小于 2，且最下面一层的节点都集中在该层最左边的连续位置上。

\subsection{如何存树}

\subsubsection{存父亲}

用一个数组记录每个节点的父亲节点：\texttt{fa}数组

\subsubsection{邻接表}

当成图来存

有根树：\texttt{vector<int> childs[n], fa[n]}

二叉树：\texttt{int lch[n], rch[n], fa[n]}
